#include<bits/stdc++.h>
using namespace std;
const double eps=1e-8;
int t,n,m;
int rua[20][20];
int gua[1<<20],dp[1<<20];
double x[20],y[20];
int gg[20]={1};
int main(){
	for(int i=1;i<=18;++i)gg[i]=gg[i-1]*2;
	for(int i=0;i<gg[18];++i){
        int j=1;
        while(j<=18&&i&gg[j-1])++j;
        gua[i]=j;
    }
    scanf("%d",&t);
    while(t--){
        memset(rua,0,sizeof rua);
        memset(dp,0x3f,sizeof dp);
        dp[0]=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                if(abs(x[i]-x[j])<eps)continue;
                double b=(x[i]*x[i]*y[j]-x[j]*x[j]*y[i])/(x[i]*x[i]*x[j]-x[j]*x[j]*x[i]);
                double a=(y[i]-x[i]*b)/(x[i]*x[i]);
                if(a>-eps)continue;
                for(int k=1;k<=n;k++)
                    if(abs(a*x[k]*x[k]+b*x[k]-y[k])<eps)rua[i][j]|=gg[k-1];
            }
        for(int i=0;i<gg[n];i++){
            int j=gua[i];
            dp[i|gg[j-1]]=min(dp[i|gg[j-1]],dp[i]+1);
            for(int k=1;k<=n;k++) dp[i|rua[j][k]]=min(dp[i|rua[j][k]],dp[i]+1);
        }
        printf("%d\n",dp[gg[n]-1]);
    }
    return 0;
}
